/**
 * 从前序和中序遍历构造二叉树
 * @param {*} preorder 二叉树的前序遍历序列
 * @param {*} inorder 二叉树的中序遍历序列
 */
class Tree {
  constructor (val) {
    this.val = val
    this.left = null
    this.right = null
  }
}


// var buildTree = function (preorder, inorder) {
//   if (!preorder.length || !inorder.length) {
//     return null;
//   }

//   let root = new Tree(preorder[0])
//   // console.log(root);
//   // # 在中序遍历序列中找到根节点的位置
//   // root_index = inorder.index(root_val)
//   let root_index = inorder.indexOf(preorder[0]) //1
//   // 构造左子树和右子树
//   const leftInorder = inorder.slice(0, root_index)
//   const rightInorder = inorder.slice(root_index + 1)
//   const leftPreorder = preorder.slice(1, root_index + 1)
//   const rightPreorder = preorder.slice(root_index + 1)
//   root.left = buildTree(leftPreorder, leftInorder)
//   root.right = buildTree(rightPreorder, rightInorder)

//   return root;
// };
// let preorder = [3, 9, 20, 15, 7]
// let inorder = [9, 3, 15, 20, 7]
// const tree = buildTree(preorder, inorder)
// console.log(tree);

/**
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历
 * @param {*} inorder 
 * @param {*} postorder 
 */
var buildTree = function (inorder, postorder) {
  // 后序遍历数组中的最后一个值为二叉树的根节点
  if (!postorder.length || !inorder.length) {
    return null;
  }
  let root = new Tree(postorder[postorder.length - 1])
  let rootIndex = inorder.indexOf(postorder[postorder.length - 1]) // 1

  const leftInorder = inorder.slice(0, rootIndex);
  const rightInorder = inorder.slice(rootIndex + 1);
  const leftPostorder = postorder.slice(0, rootIndex);
  const rightPostorder = postorder.slice(rootIndex, postorder.length - 1);

  root.left = buildTree(leftInorder, leftPostorder);
  root.right = buildTree(rightInorder, rightPostorder);

  return root;
}
let inorder = [9, 3, 15, 20, 7]
let postorder = [9, 15, 7, 20, 3]
const tree = buildTree(inorder, postorder)
console.log(tree);

// 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
// 输出：[3,9,20,null,null,15,7]